package www.com.zhongge.heap;

import java.util.Arrays;

/**
 * @ClassName MyHeap
 * @Description TODO 自定义堆==》模拟priorityQueue 的实现
 * @Author 笨忠
 * @Date 2025/7/30 11:03
 * @Version 1.0
 */
@SuppressWarnings("all")
public class MyHeap {
    //需要一个数组
    private int[] elem;
    //需要usedSize 始终指向最后一个的下一个元素
    private int usedSize;

    //构造函数
    public MyHeap() {
        this.elem = new int[10];
    }

    //初始化完全二叉树
    public void initBintry(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            elem[usedSize++] = arr[i];
        }
    }

    //构建大根堆
    public void createBigRootHeap() {
        for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {
            //向下调整路径
            siftDown(parent, usedSize);
        }
    }

    /**
     * 向下建堆 ：时间复杂度 O(n)
     * @param parent 每一棵子树的起点
     * @param usedSize 每一棵子树调整到什么时候停下（终点） ： 无论什么 child只要 >= usedSize 就说明结束了
     */
    private void siftDown(int parent, int usedSize){
        //知道父节点 求出孩子节点
        int child = 2*parent + 1;
        //在终点之前调整路径上的所有节点
        while (child < usedSize) {
            //求出左右孩子中的最大值
            if (child + 1 < usedSize && elem[child] < elem[child + 1]) {
                child = child + 1;//确保child始终指向的是最大的孩子
            }
            //比较父节点和最大孩子节点之间的最大值
            if (elem[parent] < elem[child]) {//如果孩子节点大==》就交换
                swap(child, parent);
                //父和孩子沿着路径向下调整
                parent = child;//知父
                child = parent*2 + 1;//求子
            }else {//如果父节点本来就大  就直接不用交换了直接跳出循环
                break;
            }
        }
    }

    /**
     * 交换两个数
     * @param i
     * @param j
     */
    private void swap(int i, int j) {
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }


    public void disply() {
        for (int i = 0; i < usedSize; i++) {
            System.out.print(elem[i] + " ");
        }
        System.out.println();
    }

    /**
     * 堆的插入：无论增删改查都要保持大根堆
     *  尾插法：所以要向上调整：知道孩子求父节点 然后一起沿着路径向上走
     *  向上调整 只调整一次路径
     * @param val 插入的值
     */
    public void offer(int val) {
        //首先要判满扩容
        if (isFull()) {
            elem = Arrays.copyOf(elem, 2*elem.length);
        }
        //进行尾插
        elem[usedSize] = val;
        //只调整一次路径
        siftUp(usedSize);//只有一个参数 因为另外一个参数是 0(路径的终点) 固定死的
        usedSize++;//添加后us++
    }

    /**
     * 向上调整 ： 时间复杂度O(nlogn)
     * @param child
     */
    private void siftUp(int child) {
        //知道孩子求父
        int parent = (child - 1) / 2;
        //终点是0 在0之前的路径上的节点都要调整
        while (parent >= 0) {
            if (elem[child] > elem[parent]) {//孩子只需跟父比较，因为此前该树是大根堆 所以父比孩子大
                swap(child, parent);

                //沿着路径向上移动
                child = parent;//知子
                parent = (child - 1)/2;//求父
            } else {
                break;
            }
        }
    }

    /**
     * 判满
     * @return
     */
    private boolean isFull() {
        return usedSize == elem.length;
    }

    /**
     * 删除大根堆中的元素
     *  头删法==》调整从0号位置的开始沿着向下调整
     *  如何头删？？？==》最后一个与0号下标交换
     * @return 删除过的值
     */
    public int poll() {
        //判空
        if (isEmpty()) {
            throw new ElementNullException("元素为空");
        }
        int val = elem[0];//先将0号下标的元素记录下来

        //删除：删首 首尾换 usedSize--
        swap(0, usedSize - 1);
        usedSize--;
        //然后保持大根堆：向下调整
        siftDown(0, usedSize);

        return val;
    }

    /**
     * 判空
     * @return
     */
    private boolean isEmpty() {
        return usedSize == 0;
    }

    /**
     * 获取堆顶元素
     * @return
     */
    public int peek() {
        if (isEmpty()) {
            throw new ElementNullException("元素为空");
        }
        return elem[0];
    }
}
